package datastructure.linkedlist;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020-03-18
 */
public class LinkedListDemo {

    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "张三");
        HeroNode hero2 = new HeroNode(2, "李四");
        HeroNode hero3 = new HeroNode(3, "王五");
        HeroNode hero4 = new HeroNode(3, "赵六");
//        SingleLinkedList linkedList = new SingleLinkedList();
//        linkedList.add(hero1);
//        linkedList.add(hero2);
//        linkedList.add(hero3);
//        linkedList.showList();
//        System.out.println("```````````````````````````");
//        linkedList.addByOrder(hero1);
//        linkedList.addByOrder(hero3);
//        linkedList.addByOrder(hero2);
//        linkedList.set(hero4);
//        linkedList.delete(2);
//        System.out.println(linkedList.size());
//        HeroNode heroNode = linkedList.getByReciprocal(1);
//        System.out.println(heroNode);
//        linkedList.reverse();

//        linkedList.reversePrint();
//        linkedList.showList();

        DoubleLinkedList list = new DoubleLinkedList();
        list.addByOrder(hero1);
        list.addByOrder(hero3);
        list.addByOrder(hero2);
        list.set(hero4);
        list.delete(2);
        list.showList();

    }


}

class SingleLinkedList {
    // 定义一个头节点
    private HeroNode headNode = new HeroNode(0, "");

    /**
     * 添加节点
     *
     * @param node 需要添加的节点
     */
    public void add(HeroNode node) {
        HeroNode temp = headNode;
        while (temp.getNext() != null) {
            temp = temp.getNext();
        }
        temp.setNext(node);
    }

    /**
     * 添加节点 根据id顺序
     * 思路 需要添加节点的前一个节点 temp
     *
     * @param node 需要添加的节点
     */
    public void addByOrder(HeroNode node) {
        HeroNode temp = headNode;
        // 是否存在标志位
        boolean flag = false;
        while (temp.getNext() != null) {
            // 如果temp节点的下一个id大于添加节点id 说明找到temp了
            if (temp.getNext().getId() > node.getId()) {
                break;
            } else if (temp.getNext().getId() == node.getId()) {
                // 添加节点的id存在了
                flag = true;
                break;
            }
            temp = temp.getNext();
        }
        if (flag) {
            System.out.println("元素节点已存在~~~~");
        } else {
            node.setNext(temp.getNext());
            temp.setNext(node);
        }
    }

    /**
     * 修改节点值
     *
     * @param node 需要修改的节点
     */
    public void set(HeroNode node) {
        HeroNode temp = headNode;
        while (temp != null) {
            if (node.getId() == temp.getId()) {
                temp.setName(node.getName());
                break;
            }
            temp = temp.getNext();
        }
    }

    /**
     * 删除节点
     * 找到需要删除的前一个节点
     *
     * @param id 节点id
     */
    public void delete(int id) {
        HeroNode temp = headNode;
        while (temp != null) {
            if (temp.getNext() == null) {
                break;
            }
            if (temp.getNext().getId() == id) {
                temp.setNext(temp.getNext().getNext());
            }
            temp = temp.getNext();
        }
    }

    /**
     * 计算链表长度
     *
     * @return 链表长度
     */
    public int size() {
        int size = 0;
        HeroNode temp = headNode;
        while (temp.getNext() != null) {
            size++;
            temp = temp.getNext();
        }
        return size;
    }

    /**
     * 查找倒数第index的节点
     *
     * @param index 倒数索引
     * @return 节点
     */
    public HeroNode getByReciprocal(int index) {
        HeroNode target = headNode.getNext();
        if (target == null) {
            return null;
        }
        if (index < 0 || index > size()) {
            System.out.println("传入索引存在问题");
            return null;
        }
        // 得到正序索引
        int inx = size() - index;
        for (int i = 0; i < inx; i++) {
            target = target.getNext();
        }
        return target;
    }

    /**
     * 反转
     */
    public void reverse() {
        // 若链表为空或者只有一个节点不需要反转
        if (headNode.getNext() == null || headNode.getNext().getNext() == null) {
            return;
        }
        // 定义当前节点
        HeroNode current = headNode.getNext();
        // 当前节点的下一个节点
        HeroNode currentNext;
        // 定义反转头节点
        HeroNode reverseHead = new HeroNode(0, "");
        while (current != null) {
            // 暂时保存当前节点的下一个节点
            currentNext = current.getNext();
            // 将当前节点的下一个节点指向reverse链表最前端
            current.setNext(reverseHead.getNext());
            // 将当前节点连接到reverse链表
            reverseHead.setNext(current);
            current = currentNext;
        }
        // 头节点替换 完成反转
        headNode.setNext(reverseHead.getNext());
    }

    /**
     * 显示链表
     */
    public void showList() {
        if (headNode.getNext() == null) {
            System.out.println("链表暂无数据");
            return;
        }
        HeroNode temp = headNode.getNext();
        while (temp != null) {
            System.out.println(temp);
            temp = temp.getNext();
        }
    }

    /**
     * 逆序打印
     * 借助栈
     */
    public void reversePrint() {
        HeroNode temp = headNode.getNext();
        if (temp == null) {
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        while (temp != null) {
            stack.push(temp);
            temp = temp.getNext();
        }
        while (!stack.empty()) {
            System.out.println(stack.pop());
        }
    }

}

/**
 * 模拟双向链表
 */
class DoubleLinkedList {

    private HeroNode head = new HeroNode(0, "");

    public HeroNode getHead() {
        return head;
    }

    /**
     * 添加节点
     *
     * @param node 节点
     */
    public void add(HeroNode node) {
        HeroNode temp = head;
        while (temp.getNext() != null) {
            temp = temp.getNext();
        }
        temp.setNext(node);
        node.setPre(temp);
    }

    public void addByOrder(HeroNode node) {
        HeroNode temp = head;
        // 是否存在标志位
        boolean flag = false;
        while (temp.getNext() != null) {
            // 如果temp节点的下一个id大于添加节点id 说明找到temp了
            if (temp.getNext().getId() > node.getId()) {
                break;
            } else if (temp.getNext().getId() == node.getId()) {
                // 添加节点的id存在了
                flag = true;
                break;
            }
            temp = temp.getNext();
        }
        if (flag) {
            System.out.println("元素节点已存在~~~~");
        } else {
            node.setNext(temp.getNext());
            node.setPre(temp);
            if (node.getNext() != null){
                node.getNext().setPre(node);
            }
            temp.setNext(node);
        }
    }

    /**
     * 修改节点
     */
    public void set(HeroNode node) {
        HeroNode temp = head.getNext();
        while (temp != null) {
            if (temp.getId() == node.getId()) {
                temp.setName(node.getName());
            }
            temp = temp.getNext();
        }
    }

    /**
     * 删除节点
     */
    public void delete(int id) {
        HeroNode temp = head.getNext();
        while (temp != null) {
            if (temp.getId() == id) {
                temp.getPre().setNext(temp.getNext());
                // 注意如果删除最后一个节点 不做下面判断会造成空指针
                if (temp.getNext() != null) {
                    temp.getNext().setPre(temp.getPre());
                }
            }
            temp = temp.getNext();
        }
    }

    /**
     * 遍历打印
     */
    public void showList() {
        HeroNode temp = head.getNext();
        if (temp == null) {
            System.out.println("链表暂无数据~~~~");
            return;
        }
        while (temp != null) {
            System.out.println(temp);
            temp = temp.getNext();
        }
    }

}

class HeroNode {
    private int id;
    private String name;
    private HeroNode next;
    private HeroNode pre;

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getNext() {
        return next;
    }

    public void setNext(HeroNode next) {
        this.next = next;
    }

    public HeroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public HeroNode getPre() {
        return pre;
    }

    public void setPre(HeroNode pre) {
        this.pre = pre;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}